Although modeling systems in Mechanical Computer Aided Design and in animation are expanding their geometric domain to free form surfaces, polygonal models remain the primary 3D representation used in the manufacturing, architectural, Geographic Information Systems, geoscience, and entertainment industries. Polygonal models are particularly effective for hardware assisted rendering, which is important for video-games, virtual reality, fly-through, and electronic mock-up applications involving complex Computer Aided Design models.
A polygonal model is defined by the position of its vertices (geometry), which are n-dimensional vectors, by the association between each face and its sustaining vertices (connectivity), and/or by colors, normals, and texture coordinates (properties), which do not affect the 3D geometry, but influences the way it is shaded.
In the present disclosure we will also refer to a polygonal model as a "single-resolution polygonal model".
Single-resolution polygonal models are described in detail in U.S. Pat. No. 5,825,369 "Compression of Simple Geometric Models Using Spanning Trees", Ser. No. 08/688,572 filed Jul. 30, 1996, by J. Rossignac and G. Taubin, and in U.S. patent application "Compression of Geometric Models Using Spanning Trees", Ser. No. 08/685,422 filed Jul. 30, 1996, by J. Rossignac and G. Taubin, which are here incorporated by reference in its entirety.
When the number of vertices and faces of a polygonal model is very large, the graphics rendering hardware may not be able to achieve frame rates high enough for interactive applications. Multi-resolution polygonal models are used in the prior art to solve this problem.
A multi-resolution polygonal model is a sequence of polygonal models, where each element of the sequence, called a "level of detail", or just a "level", has more vertices and faces than the previous level. The first element of the sequence is called the "lowest resolution level", and the last element of the sequence is called the "highest resolution level".
Multi-resolution polygonal models solve the problem of interacting with very large polygonal models by trading image quality for speed. Since the time required to render a frame is proportional to the complexity of the scene, rendering lower resolution levels yield higher frame rates. When there is relative motion of the object with respect to the camera, or a large distance between the object and the camera in the scene, a lower level of detail is rendered instead of the highest resolution level, which is the original polygonal model. When the scene becomes static, lower frame rates may be acceptable, and a higher resolution level can be rendered yielding higher image quality.
Prior art methods for generating multi-resolution polygonal models from single-resolution polygonal models are described in "Multi-resolution Surface Modeling", Course Notes for Siggraph'97, edited by Paul Heckbert, which is here incorporated by reference in its entirety. In all such methods the input single-resolution model becomes the highest level of detail of the generated multi-resolution model.
Many prior art methods to generate multi-resolution polygonal models are based on "vertex clustering algorithms", and the multi-resolution polygonal models produced by such methods are called "clustered multi-resolution polygonal models". In a clustered multi-resolution polygonal model the vertices of each level of detail are partitioned into disjoint subsets of vertices called "clusters", and all the vertices in each cluster are collapsed into a single vertex of the previous (lower resolution) level of detail.
Collapsing vertices may produce duplicate faces, faces with fewer comers, collapsing of faces into edges, or total collapsing of faces into single vertices. Faces which do not collapse, as well as those which collapse into faces with fewer comers, are preserved in the previous level of detail. Duplicate faces, as well as those which collapse into single vertices, are discarded in the previous level of detail. Faces which collapse into edges are optionally preserved in some methods.
One such method to generate clustered multi-resolution polygonal models is described in U.S. Pat. No. 5,448,686 "Multi-Resolution Graphic Representation Employing at Least One Simplified Model for Interactive Visualization Applications", by P. Borrel and J. Rossignac, which is here incorporated by reference in its entirety. In this method vertices of one level of detail are partitioned into clusters based on geometric proximity.
In other prior art methods to generate clustered multi-resolution polygonal models, the clustering of vertices is described as a sequence of "edge collapse" operations. An edge collapse operation identifies the two endpoints of an edge of a level, reducing the number of vertices of the level by one, and the number of triangles of the level by two. One such method is described in U.S. patent application "Surface Simplification Preserving a Solid Volume and Respecting Distance Tolerances", Ser. No. 08/742,641 filed Nov. 1, 1996, by A. Gueziec, which is here incorporated by reference in its entirety.
Switching between consecutive levels of detail may produce visual artifacts. The correspondence between vertices in one level of detail and vertices in the previous level of a clustered multi-resolution polygonal model is used in the prior art to mitigate this problem, by smoothly transitioning, or "morphing", from one level to the next interpolating the position of vertex coordinates as a function of time.
Single-resolution polygonal models and multi-resolution polygonal models are increasingly stored in file servers and exchanged over computer networks. In both cases it is desirable to compress the models to reduce the total amount of data stored and transmitted.
When transmitting a multi-resolution polygonal model it is desirable to send the information necessary to reconstruct the levels in increasing order of level of detail, i.e., from low to high resolution, so that the receiver could render a level as soon as it has all the information associated with such level, and let the user interact with it before it has all the information necessary to render the next level. This is called progressive representation and transmission.
Methods for efficiently representing single-resolution polygonal models in compressed form are known in the prior art. Methods for representing clustered multi-resolution polygonal models in progressive, but not compressed, form are also known in the prior art.
Since methods are known in the prior art for easily and efficiently triangulating arbitrary polygonal faces, many prior art methods only consider polygonal models defined by triangular meshes. A "triangular mesh" is a polygonal model in which all the faces are triangles.
One method to compress single resolution triangular meshes is described by Michael Deering in "Geometric Compression", Proceedings of ACM Siggraph'95, pp 13-20, August 1995, which is here incorporated by reference in its entirety; and in European Patent Applications "Method and apparatus for geometric compression of three-dimensional graphis", Ser. No. EP0 757 333, filed May 8, 1996, by Michael Deering, which is here incorporated by reference in its entirety. In this method a stack-buffer is used to store 16 of the previously used vertices instead of having random access to all the vertices of the model. The triangles of the mesh are partitioned into "generalized triangle meshes". Triangles which belong to the same generalized triangle mesh may share vertices, which are transmitted only once using the stack-buffer. But vertices common to triangles which belong to different generalized triangle meshes must be duplicated. In this method the connectivity of the triangular mesh is lost. The vertex positions and properties are quantized and entropy encoded.
Another such method to compress single resolution triangular meshes is described in U.S. Pat. No. 5,825,369 "Compression of Simple Geometric Models Using Spanning Trees", Ser. No. 08/688,572 filed Jul. 30, 1996, by J. Rossignac and G. Taubin, and in U.S. patent application "Compression of Geometric Models Using Spanning Trees", Ser. No. 08/685,422 filed Jul. 30, 1996, by J. Rossignac and G. Taubin, which are here incorporated by reference in its entirety. In this method the connectivity of the triangular mesh is preserved without loss of information. In this scheme the vertices of the triangular mesh are organized into a "vertex spanning tree", and the triangles into a "triangle spanning tree". The vertex spanning tree is a sub-graph of the "graph of the triangular mesh", which the graph defined by the vertices and edges of the triangular mesh. And the triangle spanning tree is a sub-graph of the "dual graph of the triangular mesh", which is the graph defined by the triangles and edges of the triangular mesh. The order of traversal of both trees define an "order for the edges of triangular mesh". The vertex positions and properties are quantized and entropy encoded. The prior art on graphs and trees is described by R. E. Tarjan in "Data Structures and Network Algorithms", SIAM, 1983; which is here incorporated by reference in its entirety.
One method for progressive transmission of triangular meshes is described by Hoppe in "Progressive Meshes", Proceedings of ACM SIGGRAPH'96, pp. 99-108; which is here incorporated by reference in its entirety. This scheme does not apply to general clustered multi-resolution polygonal models. It is restricted to clustered multi-resolution polygonal models generated by edge collapses with no change of connectivity. Another such scheme is described by Popovic et. al. in "Progressive Simplicial Complexes", Proceedings of ACM Siggraph'97, pp. 217-224, which is here incorporated by reference in its entirety. This scheme overcomes some of the limitations of Hoppe's method and allows some changes in connectivity.
The methods of Hoppe's and Popovic's build a progressive mesh representation that consists of a description of the transition from a simplified mesh to the original mesh. Hoppe represents this transition as a sequence of "vertex splits". Each of these vertex splits is specified by the index of a vertex of the mesh plus two edges incident to the given vertex. The edge split operation consists in cutting the mesh through the specified edges, resulting in the given vertex being split into two new vertices joined by an edge, and inserting two new triangles in the resulting whole. In addition, the displacements of the two new vertices with respect to the split vertex position in the previous level must be specified.
The method of Popovic et. al. is a generalization of Hoppe's scheme to lines, surfaces and volumes. A vertex split is replaced with a "generalized vertex split". With respect to the vertex split, additional information is necessary to encode whether the added vertex will add a point, a line segment, a triangle or a tetrahedron to the complex.
While Hoppe and Popovic claim that their methods can be used to compress clustered multi-resolution polygonal models generated by edge collapsing or generalized edge collapsing, these are not efficient compression schemes. They require in the order of N(log(N)) total bits of data to represent a triangular mesh of N vertices in progressive form. The other main problem with Hoppe's and Popovic's methods is that they do not apply to general clustered multi-resolution polygonal models.
On the other hand, Rossignac and Taubin method require in the order of N total bits of data to represent a single resolution mesh in compressed form, but do not apply to any multi-resolution model.
There is thus a long felt need to overcome these and other problems of the prior art. To date there is no method to efficiently represent in compressed form and progressively transmit clustered multi-resolution polygonal models.